This invention relates generally to the layout of integrated circuits. In particular, this invention relates to a method of ordering elements within an integrated circuit in order to minimize the length of connections between the elements of the integrated circuit.
In many types of integrated circuits there are a large number of well defined elements which need to be interconnected. Often the interconnections are such that there is not readily apparent sequence in which the elements should be arranged. At first glance, the elements can be randomly placed on the chip, and then the necessary interconnections can be made. This situation is in sharp contrast to semiconductor memories in which there is a natural order of the memory cells, the attached drive circuitry and the input/output circuitry. However, it is obvious that a random placement of the elements is likely to produce an unacceptably high complexity in the interconnections. Thus, it is desirable that the elements be place intelligently in order to simplify the interconnection problem. There are several possible scores that may be applied to evaluate a required set of interconnections. The one which will be addressed here is a score that approximates the distance of wiring extending from any element and sums these distances for all elements. A minimum score is, therefore, desired. Other scoring techniques are, of course, possible.
Once all the elements have been placed on the chip, the score of that particular placement can be evaluated. Of course, better scores may exist for different placement arrangements. Unfortunately, there are typically too many elements to allow the scoring for all possible arrangements. Hence, the problem exists of finding in a reasonable time near optimal or acceptable placement, as measured by the score.
One class of integrated circuits which require this type of placement are LSI and VLSI chips using structured arrays, that is, gate arrays. The layout requires fast and effective methods to automatically place large number of interrelated discrete elements. The individual elements must be placed on a two dimensional surface, and the elements have different lengths and widths. Accordingly, an associated problem is fitting these elements together so as to minimize the amount of chip area that is not being utilized.
Two methods commonly used for moving placement elements are "pair-wise interchange" and "insert and bump". These techniques have inherent deficiencies when applied to a very large two dimensional problem, especially when there are differently sized placement elements.
The "pair-wise interchange" method involves the process of finding two size-compatible elements or groups of elements that will yield an improvement in score when interchanging locations. The restriction of finding two compatibly sized objects limits the flexibility as to where an object can be placed. The additional restriction of finding two objects that will mutually improve the score also constrains the flexibility of movement. These restrictions often limit the number of possible moves, thus slowing down and inhibiting the heuristic process of evolution. The computational time required when using this method has been historically excessive when applied to large problems.
The other commonly used method, "insert and bump", provides flexibility to element movement because the elements are individually placed and inserted into new positions one at a time. This technique is generally used to solve a one dimensional placement problem where the elements need only "bump" in one direction to preserve legality. The scoring of each move includes the direct effect of inserting the element in a new position and the secondary effect of elements being offset by the move. When applying this technique to a two dimensional problem, all elements may bump both in the "x" and the "y" directions. The resolution of the overlap caused by inserting an element will involve the evaluation in both dimensions and perhaps cause a significant ripple effect. The lack of effective and fast techniques for this accommodation procedure makes this method unattractive for two dimensional placement.
Besides the above two general techniques, there are many other known methods for placing elements in a two dimensional array. Freitag in U.S. Pat. No. 3,654,615 discloses a method in which all the elements are ordered in a priority sequence according to the greatest relationship of connectivity to the remaining elements. Then the first element in the priority list is placed in a predetermined central position, and the second element is placed in an adjacent position. Thereafter, the remaining elements in the priority list are sequentially placed in positions which produce the best connnectivity score so that the placement progresses outwards.
Ballas et al in U.S. Pat. No. 3,654,072 and Eskew et al in U.S. Pat. No. 3,702,004 disclose a method in which devices associated with connectors are positioned next to the connectors. Thereafter, the devices are scored according to the percentage of connections to already placed devices. The device with the highest score is then placed in the position with the best wireability. The scores are recomputed, and the process is repeated to place all devices. Once all the devices have been initially placed, a pair-wise interchange is performed to improve the score even further. Somewhat similarly, Isett et al in U.S. Pat. No. 3,621,208 disclose a method for interconnecting devices in preassigned rows by considering the devices in a sequence according to their length of interconnections.
Raymond discloses a placement method in IBM Technical Disclosure Bulletin, Vol. 13, No. 1, June 1970 at pages 274-276. In this method, the elements are initially randomly placed. Thereafter, each device is tentatively placed in another socket. If the newly placed device is connected to a device already in that socket, then the devices are interchanged. Thereby, a wiring matrix is generated which denotes the wire length necessary for placement in every location which can be used in a linear assignment problem. The process can be iterated to obtain better scores although the scores may not be monotonically improving.
Donath in a technical article appearing in the IBM Technical Disclosure Bulletin, Vol. 17, No. 10, March 1974 at pages 3121-3125 discloses a placement method in which elements are clustered in a higher level of a hierarchy and are divided progressively in the lower levels. Initially, the elements are randomly assigned at each node of the hierarchical tree. Thereafter, interchange is used in a graph theory approach to improve the connectivity.
Lallier, Hickson and Jackson have presented a paper entitled "A System for Automatic Layout of Gate Array Chips" at the Electronic Design Automation Conference in England, Sept. 1-4, 1981 which has been distributed in TR 19.90024 by IBM in its Burlington Technical Bulletin. This method clusters associated elements in a higher hierarchical level. Elements can be initially randomly placed. Thereafter, scores can be improved by pair-wise interchange or by movement of single elements to calculate a provisional score before choosing the best placement.
Gelatt, Jr. et al in U.S. Pat. No. 4,495,559 disclose an iterative interchange method which is allowed to converge non-montonically.